package com.lihui.hash;

import java.security.Key;

/**
 * @Author 比特就业课
 * @Date 2022-11-15
 */
public class HashBucket {
    // 定义一个节点对象
    private static class Node {
        int key;
        int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 定义哈希桶
    private Node[] bucket;
    // 当前有效元素的个数
    private int size;
    // 定义负载因子
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBucket () {
        bucket = new Node[8];
    }

    /**
     * 写入操作
     * @param key
     * @param value
     * @return
     */
    public int put (int key, int value) {
        int index = key % bucket.length;
        Node current = bucket[index];
        while(current != null){
            if(current.key == key){
                int oldValue = current.value;
                current.value = value;
                return oldValue;
            }
            current = current.next;
        }
        Node node = new Node(key,value);
        node.next = bucket[index];
        bucket[index] = node;
        size++;
        if(loadFactor() >= DEFAULT_LOAD_FACTOR){
            resize();
        }
        return 0;
    }


    //扩容
    private void resize() {
        //创建一个新的数组，大小为原来数组的二倍
        Node[] array = new Node[bucket.length * 2];
        //遍历数组，取出所有元素重新hash
        for (int i = 0; i < bucket.length; i++){
            //取出第一个结点，向下遍历
            Node current = bucket[i];
            while (current != null){
                //记录下一个结点
                Node nextNode = current.next;
                //重新计算位置
                int index = current.key % array.length;
                //结点放入hash桶中
                current.next = array[index];
                array[index] = current;
                //移动到下一个结点
                current = current.next;
            }
        }
        bucket = array;
    }

    private float loadFactor() {
        return size * 1.0f / bucket.length;
    }

    public int get (int key) {
        //计算位置
        int index = key % bucket.length;
        //取出第一个结点
        Node current = bucket[index];
        //向下遍历
        while(current != null){
            //找到目标值
            if(current.key == key){
                return current.value;
            }
        }
        return -1;
    }





}
